import java.util.*;


public class OrdenacionRapida implements Ordenacion {  
    private static int umbral; 
    private static java.util.Random rand = new java.util.Random();
    private static Comparable pivote, tmp;
    private static int i=0, j=0, x=0;
	
    public OrdenacionRapida (int u) {
        umbral = u;
    }   
    private static void intercambiar (Comparable [] v, int a, int b) {
        tmp = v[a];
        v[a] = v[b];
        v[b] = tmp;
    }    
    private static void qsort (Comparable [] v, int esq, int der) {
	if (esq + umbral <= der) {            
            x = esq + (Math.abs(rand.nextInt())) % (der-esq);                   
            pivote = v[x];                        
            intercambiar (v, esq, x);  
            i = esq + 1;
            j = der;
            while(i <= j) {                
                while (i <= der && v[i].esMenorQue(pivote)) i++;
                while (v[j].esMayorQue(pivote)) j--;
                if (i <= j) {
                    intercambiar (v, i, j);
                    i++;
                    j--;
                }
            }
            intercambiar (v, esq, j);
            qsort (v, esq, j-1);
            qsort (v, j+1, der);
        }
    }    
    public void ordenar (Comparable [] v) {
	qsort (v, 0, v.length - 1);
	if (umbral > 1)
	    (new OrdenacionPorInsercion()).ordenar(v);
    }    
	
    public String toString() {
        return "Ordenacion Rapida";
    }
}
